import functools

class Envelop:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.n = 1

def lowerBound(arr, begin, end, val):
    while begin<end:
        print(begin, end)
        mid = (begin+end)//2
        if arr[mid]<val: begin=mid+1
        else: end=mid
    return begin

class Solution(object):
    def maxEnvelopes(self, envelopes):
        envs = [Envelop(env[0], env[1]) for env in envelopes]
        def cmp(e1, e2):
            if e1.x!=e2.x: return e1.x-e2.x
            elif e1.y!=e2.y: return e2.y-e1.y
            else: return 0
        envs.sort(key=functools.cmp_to_key(cmp))

        if len(envs)==0: return 0
        tail = [0] * len(envs)
        length = 1
        tail[0] = envs[0].y
        for e in envs:
            if e.y<tail[0]:
                tail[0] = e.y
            elif e.y>tail[length-1]:
                tail[length] = e.y
                length+=1
            else:
                i = lowerBound(tail, 0, length-1, e.y)
                tail[i] = e.y
        return length